package 中等.滑动窗口;

import java.util.Arrays;

/**
 * 给你一个下标从 0 开始的整数数组 nums 和一个 非负 整数 k 。
 * 在一步操作中，你可以执行下述指令：
 * 在范围 [0, nums.length - 1] 中选择一个 此前没有选过 的下标 i 。
 * 将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数。
 * 数组的 美丽值 定义为数组中由相等元素组成的最长子序列的长度。
 * 对数组 nums 执行上述操作任意次后，返回数组可能取得的 最大 美丽值。
 * 注意：你 只 能对每个下标执行 一次 此操作。
 * 数组的 子序列 定义是：经由原数组删除一些元素（也可能不删除）得到的一个新数组，且在此过程中剩余元素的顺序不发生改变。
 *
 * @ https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/description/?envType=daily-question&envId=2024-06-15
 * @date 2024/06/15
 */
public class 数组的最大美丽值_2779 {

    public static void main(String[] args) {

    }

    /**
     * 排序+滑动窗口
     * 1，注意选择某个将 nums[i] 替换为范围 [nums[i] - k, nums[i] + k] 内的任一整数，不是指的数组索引，而是实际值
     * 所以排序不会影响答案
     * 且最后的答案为某个数在数组中出现的次数
     * 2，有交集说明[0,1]可以变成一个数
     * num[0]+k >= nums[1]-k
     */
    public int maximumBeauty(int[] nums, int k) {
        int max = 0;
        Arrays.sort(nums);
        int left = 0, right = 0;

        while (right < nums.length) {

            while (right < nums.length && nums[right] - nums[left] <= 2 * k) {
                right++;
            }
            max = Math.max(max, right - left);

            left++;
        }

        return max;
    }

    /**
     * 滑动窗口
     * 先排序，left 找到 <= nums[left] + k*2 右边最大的索引 right
     */
    public int maximumBeauty2(int[] nums, int k) {
        int ans = 1;
        Arrays.sort(nums);
        int left = 0, right = 0;
        while (right < nums.length) {
            if (nums[right] - nums[left] > k * 2) {
                left++;
                continue;
            }
            ans = Math.max(ans, right - left + 1);
            right++;
        }

        return ans;
    }
}
